import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class KMeansExample {

    public static void main(String[] args) {

        // 生成100个具有随机兴趣爱好和生活习惯的学生
        List<Student> students = generateStudents(100);

        // 每个宿舍的容量为10人
        int capacity = 6;
        // 计算需要的宿舍数量
        int k = (int) Math.ceil(students.size() / (double) capacity);

        // 初始化聚类中心点
        List<Cluster> clusters = initClusters(students, k, capacity);

        // 迭代聚类
        int maxIterations = 100;
        for (int i = 0; i < maxIterations; i++) {
            // 将学生分配到最近的聚类中心点

            assignStudentsToClusters(students, clusters);
            // 重新计算聚类中心点
            boolean converged = recalculateClusters(clusters);
            if (converged) {
                break;
            }
        }

        // 输出宿舍分配结果
        System.out.println("宿舍分配结果：");
        int dormNumber = 1;
        for (Cluster cluster : clusters) {
            System.out.println("宿舍" + dormNumber++ + "：");

            for (int i = 0; i < cluster.getPoints().size(); i++) {
                Student student1=cluster.getPoints().get(i);
                System.out.println(student1.getName());
            }

            for (Student student : cluster.getPoints()) {

                System.out.println(student.getName());
            }
            System.out.println();
        }
    }

    /**
     * 生成指定数量的随机学生
     */
    private static List<Student> generateStudents(int num) {
        List<Student> students = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            Random random = new Random();

            String name = "学生" + i;

            int hobby = random.nextInt(5);
            int habit = random.nextInt(5);
            students.add(new Student(name, hobby, habit));
        }
        return students;
    }

    /**
     * 初始化聚类中心点
     */
    private static List<Cluster> initClusters(List<Student> students, int k, int capacity) {
        List<Cluster> clusters = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < k; i++) {
            List<Student> points = new ArrayList<>();
            Point center = new Point(random.nextDouble(), random.nextDouble());
            //System.out.println("center:"+center.getX()+"y:"+center.getY());
            Cluster cluster = new Cluster(i, points, center, capacity);
            clusters.add(cluster);
        }
        return clusters;
    }

    /**
     * 将学生分配到最近的聚类中心点
     */
    private static List<Cluster> assignStudentsToClusters(List<Student> students, List<Cluster> clusters) {
        for (Student student : students) {
            int i = 0;
            Cluster closestCluster = null;
            double smallestDistance = Double.MAX_VALUE;
            for (Cluster cluster : clusters) {
                double distance = Point.distance(student, cluster.getCenter());
                if (distance < smallestDistance) {
                    smallestDistance = distance;
                    closestCluster = cluster;
                }
            }
            //System.out.println(student.getName());
            closestCluster.addPoint(student);

        }
        return clusters;
    }

    /**
     * 重新计算聚类中心点
     */
    private static boolean recalculateClusters(List<Cluster> clusters) {
        boolean converged = true;
        for (Cluster cluster : clusters) {
            List<Student> points = cluster.getPoints();
            if (points.isEmpty()) {
                System.out.println("空");
                continue;
            }
            Point newCenter = Point.average(points);
            if (!newCenter.equals(cluster.getCenter())) {
                converged = false;
                cluster.setCenter(newCenter);
                cluster.clearPoints();
            }
        }
        return converged;
    }
}

/**
 * 学生类，包含姓名、兴趣爱好和生活习惯属性
 */
class Student extends Point {
    private String name;
    private int hobby; // 0~4，0表示最感兴趣，4表示最不感兴趣
    private int habit; // 0~4，0表示最适应，4表示最不适应

    public Student(String name, int hobby, int habit) {
        super(Math.random(), Math.random());
        this.name = name;
        this.hobby = hobby;
        this.habit = habit;
    }



    public String getName() {
        return name;
    }

    public int getHobby() {
        return hobby;
    }

    public int getHabit() {
        return habit;
    }
}

/**
 * 二维点类，包含x和y坐标属性
 */
class Point {
    private double x;
    private double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }

    /**
     * 计算两个点之间的欧氏距离
     */
    public static double distance(Point p1, Point p2) {
        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    /**
     * 计算一组点的中心点
     */
    public static Point average(List<? extends Point> points) {
        double sumX = 0;
        double sumY = 0;
        for (Point point : points) {
            sumX += point.x;
            sumY += point.y;
        }
        double avgX = sumX / points.size();
        double avgY = sumY / points.size();
        return new Point(avgX, avgY);
    }
}

/**
 * 聚类类，包含编号、包含的点、中心点和容量属性
 */
class Cluster {
    private int number;
    private List<Student> points;
    private Point center;
    private int capacity;

    public Cluster(int number, List<Student> points, Point center, int capacity) {
        this.number = number;
        this.points = points;
        this.center = center;
        this.capacity = capacity;
    }

    public int getNumber() {
        return number;
    }

    public List<Student> getPoints() {
        return points;
    }

    public Point getCenter() {
        return center;
    }

    public int getCapacity() {
        return capacity;
    }

    /**
     * 向该聚类添加一个点
     */
    public void addPoint(Student point) {
        points.add(point);
    }

    /**
     * 清空该聚类的点
     */
    public void clearPoints() {
        points.clear();
    }

    /**
     * 设置该聚类的中心点
     */
    public void setCenter(Point center) {
        this.center = center;
    }
}